#pragma once
#include <vector>
#include <algorithm>

namespace zzzyh
{
	template<class T>
	class Less
	{
	public:
		bool operator()(const T& t1, const T& t2)
		{
			return t1 < t2;
		}
	};

	template<class T>
	class Greate
	{
	public:
		bool operator()(const T& t1, const T& t2)
		{
			return t1 > t2;
		}
	};

	template<class T, class Container = std::vector<T>,class Com = Less<T>>
	class priority_queuq
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
			xiangshangtiaozheng(size() - 1);
		}
		const T& top()
		{
			return _con.front();
		}
		void pop()
		{
			std::swap(_con.front(), _con.back());
			_con.pop_back();
			xiangxiatiaozheng(0,size());
		}
		size_t size()
		{
			return _con.size();
		}
		bool empty() {
			return _con.empty();
		}
	private:
		Container _con;
		void xiangshangtiaozheng(int i) {
			Com com;
			while (i > 0 && com(_con[i], _con[(i - 1) / 2])) {
				std::swap((_con[i]), (_con[(i - 1) / 2]));
				i = (i - 1) / 2;
			}
		}
		void xiangxiatiaozheng( int i, int sz) {
			Com com;
			while (i * 2 + 1 < sz) {
				int chile = i * 2 + 1;
				if (chile + 1 < sz && com(_con[chile + 1], _con[chile])) {
					chile++;
				}
				if (com(_con[chile],_con[i] )) {
					std::swap(_con[i], _con[chile]);
					i = chile;
				}
				else return;
			}
		}
	};

}

//#include <iostream>
//#include <cstring>
//#include <vector>
//#include <functional>
//using namespace std;
//
//template <class T, class Container = std::vector<T>, class Compare = less<T>>
//class priority_queue {
//public:
//    priority_queue()
//        :c(vector<T>()),
//        Com(less<T>())
//    {
//
//    }
//    template <class InputIterator>
//    priority_queue(InputIterator first, InputIterator last)
//    {
//        while (first != last)
//        {
//            c.push(*first);
//            first++;
//        }
//    }
//    bool empty() const
//    {
//        return  c.empty();
//    }
//    size_t size() const
//    {
//        return c.size();
//    }
//    const T& top() const
//    {
//        return c.front();
//    }
//    void push(const T& x)
//    {
//        c.push_back(x);
//        AdjustUp(c.size()-1);
//    }
//    void pop()
//    {
//        swap(c[0], c[c.size() - 1]);
//        c.pop_back();
//        AdjustDown(0);
//    }
//private:
//    void AdjustUp(int child)
//    {
//        int parent = (child - 1) / 2;
//        while (Com(c[parent], c[child]))
//        {
//            swap(c[parent], c[child]);
//            child = parent;
//            parent = (child - 1) / 2;
//        }
//    }
//    void AdjustDown(int parent)
//    {
//        int child = parent * 2 + 1;
//        while (child < c.size())
//        {
//            if (child + 1 < c.size() && Com(c[child], c[child + 1]))
//                child++;
//            if (Com(c[parent], c[child]))
//            {
//                swap(c[child], c[parent]);
//                parent = child;
//                child = parent * 2 + 1;
//            }
//            else
//                return;
//        }
//    }
//private:
//    Container c;
//    Compare Com;
//
//};
//
//int main() 
//{
//    priority_queue<int> que;
//    que.push(10);
//    que.push(20);
//    que.push(50);
//    que.push(40);
//    que.push(80);
//    que.push(80);
//    que.push(50);
//    que.push(60);
//    que.push(30);
//    cout << que.top()<<endl;
//    que.pop();
//    que.pop();
//    cout << que.top()<<endl;
//
//}